package com.lw.leetcode.str.c;

/**
 * Created with IntelliJ IDEA.
 * 1392. 最长快乐前缀
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/28 16:49
 */
public class LongestPrefix {

    public static void main(String[] args) {
        LongestPrefix test = new LongestPrefix();

        // abab
//        String str = "ababab";

        // ""
//        String str = "a";

        // "a"
//        String str = "aa";

        // ""
//        String str = "bba";

        // aaaaaaaa
//        String str = "aaaaaaaaa";

        // b
//        String str = "babbb";

        // abab
//        String str = "level";

        // ""
        String str = "abc";

        //
//        String str = Utils.getStr(1000, 'a', 'z');

        String s = test.longestPrefix(str);
        System.out.println(s);
    }

    public String longestPrefix(String s) {
        int length = s.length();
        if (length == 1) {
            return "";
        }
        int[] arr = new int[length];
        char[] chars = s.toCharArray();
        int i = 0;
        int j = -1;
        arr[0] = -1;
        while (i < length - 1) {
            if (j == -1 || chars[i] == chars[j]) {
                i++;
                j++;
                arr[i] = j;
            } else {
                j = arr[j];
            }
        }
        while (j != -1 && chars[i] != chars[j]) {
            j = arr[j];
        }
        return s.substring(0, j + 1);
    }

}
